package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-number-of-removals-to-make-mountain-array/
 * @create 2025/9/4 20:34
 * @since JDK17
 */

public class Solution70 {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length, ans = Integer.MIN_VALUE;
        int[] dp1 = new int[n], dp2 = new int[n];
        for (int i = 0; i < n; i++) {
            dp1[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp1[i] = Math.max(dp1[i], dp1[j] + 1);
                }
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            dp2[i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (nums[i] > nums[j]) {
                    dp2[i] = Math.max(dp2[i], dp2[j] + 1);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (dp1[i] > 1 && dp2[i] > 1) { // 左边合法且右边也合法
                ans = Math.max(ans, dp1[i] + dp2[i] - 1);
            }
        }
        return n - ans;
    }
}
